package com.xy6.struct.tree;

/*
 * Copyright Walker Studio
 * All Rights Reserved.
 * 
 * 文件名称： ManyNodeTree.java
 * 摘 要：
 * 作 者： Walker
 * 创建时间： 2013-03-19
 */

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 多叉树生成、遍历工具
 * <pre>
 * 创建一个节点bean，保存节点id、父节点id、及内容
 * 创建一个多叉树的节点bean，包含一个节点bean，一个子节点集合
 * </pre>
 * 
 * @author Walker
 * @version 1.0.0.0
 */
public class ManyNodeTree {
	/** 树根 */
	private ManyTreeNode root;

	/**
	 * 构造函数
	 */
	public ManyNodeTree() {
	}

	/**
	 * 向指定多叉树节点添加子节点
	 * 
	 * @param manyTreeNode 多叉树节点
	 * @param child 节点
	 */
	public void addChild(ManyTreeNode child) {
		List<ManyTreeNode> nodes = getNodes();
		if (null == nodes) {
			this.setRoot(child);
		}
		for (ManyTreeNode item : nodes) {
			if (item.getData().getNodeId().equals(child.getData().getParentId())) {
				item.getChildList().add(child);
				break;
			}
		}
	}

	/**
	 * 添加子节点
	 * 
	 * @param child
	 */
	public void addChild(TreeNode child) {
		addChild(new ManyTreeNode(child));
	}

	/**
	 * 添加子节点
	 * 
	 * @param manyTreeNode
	 * @param child
	 */
	public void addChild(ManyTreeNode manyTreeNode, TreeNode child) {
		manyTreeNode.getChildList().add(new ManyTreeNode(child));
	}
	
	/**
	 * 获取所有节点集合
	 * 
	 * @return
	 */
	public List<ManyTreeNode> getNodes() {
		return iteror(getRoot());
	}

	/**
	 * 获取所有节点集合
	 * 
	 * @return
	 */
	public List<ManyTreeNode> getNodesBFS() {
		return iterorBFS(getRoot());
	}
	
	/**
	 * 从根节点开始，遍历一棵子树
	 * <p>深度优先算法
	 * 
	 * @param node
	 * @return
	 */
	private List<ManyTreeNode> iteror(ManyTreeNode node) {
		if (null == node) {
			return null;
		}
		List<ManyTreeNode> nodes = new ArrayList<>();
		nodes.add(node);
		for (ManyTreeNode index : node.getChildList()) {
			List<ManyTreeNode> temp = iteror(index);
			if (temp != null) {
				nodes.addAll(temp);
			}
		}
		return nodes;
	}
	
	/**
	 * 从根节点开始，遍历一棵子树
	 * <p>广度优先算法
	 * 
	 * @param node
	 * @return
	 */
	public List<ManyTreeNode> iterorBFS(ManyTreeNode node) {
		List<ManyTreeNode> nodes = new ArrayList<>();
		
		Deque<ManyTreeNode> nodeDeque = new ArrayDeque<ManyTreeNode>();
		nodeDeque.add(node);
		while (!nodeDeque.isEmpty()) {
			node = nodeDeque.pollFirst();
			nodes.add(node);
			//获得节点的子节点，对于二叉树就是获得节点的左子结点和右子节点
			List<ManyTreeNode> children = node.getChildList();
			if (children != null && !children.isEmpty()) {
				for (ManyTreeNode child : children) {
					nodeDeque.add(child);
				}
			}
		}
		return nodes;
	}
	
	public ManyTreeNode getRoot() {
		return root;
	}

	public void setRoot(ManyTreeNode root) {
		this.root = root;
	}

}
